#ifndef __RBTREE__
#define __RBTREE__

typedef int KEYTYPE;
typedef struct _RBTNode {
	struct _RBTNode* Parent;
	struct _RBTNode* Left;
	struct _RBTNode* Right;

    enum {RED, BLACK} Color;

	KEYTYPE key;
    void* data;

    int x,y,spreadWidth,id,parentId;

} RBTNode;

RBTNode* parentOf(RBTNode* node);
RBTNode* leftOf(RBTNode* p);
RBTNode* rightOf(RBTNode* p);
int colorOf(RBTNode* p);

RBTNode* rbtree_createNode(KEYTYPE NewData);
void rbtree_destroyNode(RBTNode* Node);
void rbtree_destroyTree(RBTNode* Tree);

RBTNode* rbtree_searchNode(RBTNode* Tree, KEYTYPE Target);
RBTNode* rbtree_searchMinNode(RBTNode* Tree);

void rbtree_insertNode(RBTNode** Tree, RBTNode* NewNode);
RBTNode* rbtree_removeNode(RBTNode** Root, KEYTYPE Target);
RBTNode* rbtree_removeNode2(RBTNode** Root, RBTNode* Target);

void rbtree_rotateLeft(RBTNode** Root, RBTNode* Parent);
void rbtree_rotateRight(RBTNode** Root, RBTNode* Parent);
void rbtree_rebuildAfterInsert(RBTNode** Tree, RBTNode* NewNode);
void rbtree_rebuildAfterRemove(RBTNode** Root, RBTNode* X);

// for display:
void rbtree_printTree(RBTNode* Node, int x, int y, int BlackCount);
void rbtree_printTree2(RBTNode* Root, int* numNodes);
void rbtree_makeTreePoints(RBTNode* Root, RBTNode* nodes[], int* numNodes);


#endif


